#include <stdio.h>
#include <stdlib.h>

// 归并排序： 将一个数组中两个相邻有序空间合并成一个

// 参数说明
// a -- 包含两个有序区间的数据
// start -- 第一个有序区间的起始地址
// mid -- 第一个有序区间的结束地址，也是第二个有序区间的起始地址
// end -- 第二个有序区间的结束地址
// int a[] ==> int *a
void Merge(int a[], int start, int mid, int end)
{
	//tmp是汇总2个有序区间的临时区间
	int* tmp = (int*)malloc((end - start + 1) * sizeof(int));
	int L = start; // 第一个有序区的索引
	int r = mid + 1; // 第二个有序区的索引
	int k = 0; // 临时区域的索引
	int i;
	while(L <= mid && r <= end)
	{
		if( a[L] <= a[r])
		{
			tmp[k++] = a[L++];
		}
		else
		{
			tmp[k++] = a[r++];
		}
	}
	
	for(i=L; i<mid + 1; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
	for(i=r; i< end + 1; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
	
	while(L <= mid+1)
	{
		tmp[k++] = a[L++];
	}
	while(r <= end+1)
	{
		tmp[k++] = a[r++];
	}

	for(i = start; i < end+1; i++)
	{
		a[i] = tmp[i - start];
		printf("%d ", a[i]);
	}
	printf("\n");
	free(tmp);
	tmp = NULL;
	
	return;
}

void MergeSort(int a[], int start, int end)
{
	int mid;
	if(start == end)
	{
		return;
	}
	mid = (start + end) >> 1;
	MergeSort(a, start, mid);
	MergeSort(a, mid+1, end);
	Merge(a, start, mid, end);
	
	return;
}

int main()
{
   /*  Write C code in this online editor and run it. */
    int a[] = {8, 7, 6, 5, 4, 3, 2, 1};
    MergeSort(a, 0, 7);
   
    return 0;
}

/*
8 

7 8 
6 

5 6 
7 8 

5 6 7 8 
4 

3 4 
2 

1 2 
3 4 

1 2 3 4 
5 6 7 8 

1 2 3 4 5 6 7 8 
*/